#include <bits/stdc++.h>
using namespace std;
class Node{
public:
    int data;
    Node* pNext;
    Node(int d,Node* p= nullptr){
        data = d;
        pNext = p;
    }
};
Node* Merge(Node* phead1,Node* phead2)
{
    Node* temp1 = phead1;
    Node* temp2 = phead2;
    if(phead1 == nullptr)
        return phead2;
    else if(phead2 == nullptr)
        return phead1;
    Node* mMergehead = nullptr;
    if(phead1->data<phead2->data){
        mMergehead = phead1;
        mMergehead->pNext = Merge(phead1->pNext,phead2);
    }
    else if(phead1->data>=phead2->data)
    {
        mMergehead = phead2;
        mMergehead->pNext = Merge(phead1,phead2->pNext);
    }
}
int main() {
    Node* a = new Node(1);
    Node* b = new Node(3);
    Node* c = new Node(5);
    Node* d = new Node(7);
    Node* e = new Node(2);
    Node* f = new Node(4);
    Node* g = new Node(6);
    Node* h = new Node(8);
    a->pNext = b;
    b->pNext = c;
    c->pNext = d;

    e->pNext = f;
    f->pNext = g;
    g->pNext = h;
    Node* MergeNode = nullptr;
    MergeNode = Merge(a,e);
    while(MergeNode)
    {
        cout<<MergeNode->data<<endl;
        MergeNode = MergeNode->pNext;
    }

    delete a,b,c,d,e,f,g,h;
    return 0;
}
